16. 3Sum Closest [M]

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

思路

这个问题等于是3SUM又升级了，因为这里现在是最接近的结果，所以Hashmap的思路基本没用了，因为必须得要循环找到所有可能。当然，这个题目有个限制就是只有唯一的结果，所以，如果发现完全相等的，也就可以停下来了。

但是解题思路还是可以参考3SUM，算法基本一样，有些地方需要修改一下。首先，因为是找最接近的，所以要考虑所有情况，left循环到length-2

  1.     for (int left = 0; left < nums.length-2; left++)

然后还是mid和right分别从两端往中央扫描，如果mid+right还比较小，那就需要mid右移，反之right左移（每次如果有最小的就存下来）

Alt text

我们可以写出如下的代码:

  1.  mid = left+1; right = nums.length-1;
  2.  while(mid < right)
  3.  {
  4.       int tmp = target-nums[left];
  5.       if(abs(tmp - nums[mid] + nums[right]) < abs(target-Min))
  6.           Min = nums[left] + nums[mid] + nums[right]);
  7.       if(nums[mid] + nums[right] == tmp)
  8.               return Min;
  9.       else if(nums[mid] + nums[right] < tmp)
  10.               mid++;
  11.       else
  12.              right--;
  13.  }

代码

  1. public class Solution {
  2.     public int threeSumClosest(int[] nums, int target) {       
  3.         Arrays.sort(nums);
  4.         int mid,right;
  5.         if(nums.length < 3)
  6.             return 0;
  7.         int Min = nums[0]+nums[1]+nums[2];
  8.         //left要循环全部
  9.         for (int left = 0; left < nums.length-2; left++) {
  10.             mid = left+1; right = nums.length-1;
  11.             int tmp = target-nums[left];
  12.             while(mid < right)
  13.             {
  14.                 if(Math.abs(tmp - nums[mid] - nums[right]) <Math.abs(target - Min))  //每次查看是不是最小的情况
  15.                     Min = nums[left]+ nums[mid] + nums[right];
  16.                 if(nums[mid] + nums[right] == tmp)
  17.                 {
  18.                     return target;   //因为只有一种答案所以可以直接返回
  19.                 }
  20.                 else if(nums[mid] + nums[right] < tmp)
  21.                     mid++;
  22.                 else
  23.                     right--;
  24.             }
  25.         }
  26.         return Min;
  27.     }
  28. }